//ListNode* reverseList(ListNode* head) {
//    if (head == nullptr || head->next == nullptr)
//        return head;
//    ListNode* tmp = reverseList(head->next);
//    head->next->next = head;
//    head->next = nullptr;
//    return tmp;
//}
//ListNode* addInList(ListNode* head1, ListNode* head2) {
//    // write code here
//    ListNode* nh1 = reverseList(head1);
//    ListNode* nh2 = reverseList(head2);
//    int tmp = 0;
//    ListNode* newhead = new ListNode(0);
//    ListNode* cur = newhead;
//    while (nh1 != nullptr || nh2 != nullptr || tmp != 0)
//    {
//        if (nh1 != nullptr)
//        {
//            tmp += nh1->val;
//            nh1 = nh1->next;
//        }
//        if (nh2 != nullptr)
//        {
//            tmp += nh2->val;
//            nh2 = nh2->next;
//        }
//        cur->next = new ListNode(tmp % 10);
//        tmp /= 10;
//        cur = cur->next;
//    }
//
//    return reverseList(newhead->next);
//
//}